Für eine praktische Implementierung des Diffie-Hellman-Verfahrens wird eine große Primzahl $p$ verwendet (in der Größenordnung $1024$ bis $2048$ Bit).

\begin{itemize}
\item
Welche Gefahr besteht für die Sicherheit des Systems, wenn man $g = m + p \Z$ verwendet, wobei $m \in \{ 1, \ldots, p-1 \}$ einfach zufällig gewählt wird? \emph{Hinweis:} Welche Ordnung hat eine Primitivwurzel modulo $p$? Was passiert, wenn die Ordnung von $g$ kleiner ist?

\item
$p$ sei von der speziellen Form $p = 2q + 1$, wobei $q$ ebenfalls prim ist. Wie findet man ein Element $g \in (\Z/p\Z)^*$, dessen Ordnung mindestens $q$ ist. \emph{Hinweis:} Welche Element-Ordnungen können in $(\Z/p\Z)^*$ überhaupt auftreten?
\end{itemize}

Zu 1. \\
Eine Primitivwurzel modulo $p$ hat die Ordnung $p-1$.

Wenn $m$ zufällig gewählt wird, kann es vorkommen, dass m keine Primitivwurzel zu der Gruppe ($\Z/p\Z$) bildet. Eine Primitivwurzel $m^k$ mit $1<k<=p-1$ bildet eine Untergruppe $U$, die genauso groß wie seine Hauptgruppe $G$ ist und alle Elemente der Hauptgruppe genau einmal abbildet. Ist $m$ nun zufällig gewählt, kann es passieren, dass die Menge der Elemente der Untergruppe kleiner ist als die der Hauptgruppe. Damit gilt $|U|<|G|$. Es geht sozusagen auch die Bijektivität verloren
Die Untergruppe bildet somit nicht alle Elemente der Hauptgruppe ab. Die Menge der Zahlen wird also kleiner und macht es dem Angreifer leichter. \\


Zu 2.

Die Gruppe hat gemäß Theorem 3.22.1 die Ordnung $p - 1 = 2q + 1 - 1 = 2q$. Gemäß Theorem 3.10.9 teilt die Ordnung jeder Untergruppe die Ordnung der Gruppe, wenn diese endlich ist. Folglich ist in diesem Fall die Ordnung jeder möglichen Untergruppe in der Menge $\lbrace 1, 2, q, 2q\rbrace$ enthalten.

Gesucht sind nun alle Untergruppen, deren Ordnung mindestens $q$ ist. Es handelt sich somit um die Untergruppen, deren Ordnung in $\lbrace q, 2q\rbrace$ enthalten ist. Es muss deshalb lediglich geprüft werden, ob die Ordnung von $g$ in $\lbrace 1, 2\rbrace$ enthalten ist, d.h. ob entweder $g^1=1$  oder $g^2=1$ gilt (Korollar 4.14.3). Alle Untergruppen, die keine dieser Bedingungen erfüllen, d.h. $g^1 \neq 1$ und $g^2 \neq 1$, habe dann entweder die Ordnung $q$ oder $2q$.

Tipp:
Wenn Sie die Ordnung der Gruppe kennen, wissen Sie, welche Zahlen als Ordnungen überhaupt auftreten können. Die Ordnung eines Gruppenelements teilt immer die Ordnung der Gruppe, d.h. als Elementordnungen können nur Teiler der Gruppenordnung vorkommen. Jetzt schauen Sie sich die konkrete Gruppenordnung mal an...